import java.rmi.dgc.Lease;
import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-04-04
 * Time: 23:17
 */


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class CBTInserter {

    public TreeNode root;

    public CBTInserter(TreeNode root) {
        this.root=root;
    }

    public int insert(int v) {
        // 1. 如果是第一次插入
        if(this.root==null){
            root=new TreeNode(v);
            return -1;
        }
        // 2. 不是第一次插入
        TreeNode node=new TreeNode(v);
        // 使用层序遍历
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(this.root);
        while(!queue.isEmpty()){
            TreeNode parent=queue.poll();
            if(parent.left!=null){
                queue.offer(parent.left);
            }else{
                // 只要遇见一个节点的子树为空
                // 那么节点就是要插入到这个位置
                // 该节点就是父亲节点
                parent.left=node;
                return parent.val;
            }
            if(parent.right!=null){
                queue.offer(parent.right);
            }else{
                parent.right=node;
                return parent.val;
            }
        }
        return -1;
    }

    public TreeNode get_root() {
        return this.root;
    }



//     方法二: 二叉树的序列化
//     对每个节点进行编号, root 为 1
//     那么 left = root*2, right=root*2+1
//     对应就是 root 的编号 左移 1 位, 最后一位 left 添 0 , right 添 1
//     那么 先遍历一遍树, 得到新插入的节点的编号
//     遍历该编号的每一个二进制位,
//     从第一个 1  后面的位开始, 为 1 则左移, 为 0 则右移
//     即可移动到新节点的父亲节点
//    int cnt;
//    TreeNode root;
//
//    public CBTInserter(TreeNode root) {
//        this.cnt = 0;
//        this.root = root;
//
//        Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
//        queue.offer(root);
//
//        while (!queue.isEmpty()) {
//            ++cnt;
//            TreeNode node = queue.poll();
//            if (node.left != null) {
//                queue.offer(node.left);
//            }
//            if (node.right != null) {
//                queue.offer(node.right);
//            }
//        }
//    }
//
//    public int insert(int val) {
//        ++cnt;
//        TreeNode child = new TreeNode(val);
//        TreeNode node = root;
//        int highbit = 31 - Integer.numberOfLeadingZeros(cnt);
//        for (int i = highbit - 1; i >= 1; --i) {
//            if ((cnt & (1 << i)) != 0) {
//                node = node.right;
//            } else {
//                node = node.left;
//            }
//        }
//        if ((cnt & 1) != 0) {
//            node.right = child;
//        } else {
//            node.left = child;
//        }
//        return node.val;
//    }
//
//    public TreeNode get_root() {
//        return root;
//    }
}
